In a wireless cellular communication system, the procedure of establishing communication between a mobile terminal or User Equipment (UE) and a base station is called random access. Such random access can be implemented using a random access channel (RACH) in, for example, an orthogonal frequency division multiplexing (OFDM) communication system or a single carrier frequency division multiplexing (SC-FDMA) communication system. Random access enables the establishment of the uplink from a UE to a base station. Using the RACH, a UE can send a notification to the network indicating that the UE has data to transmit. Receipt of the notification at the base station allows the base station to estimate the UE timing, to thereby realize uplink synchronization between the UE and the base station.
The random access channel (RACH) typically consists of a ranging signal or a preamble. The preamble is designed to allow the base station to detect the random access attempt within target detection and false alarm probabilities, and to minimise the impact of collisions on the RACH, as is known in the art. Moreover, the base station should be able to detect several simultaneous random preambles sent from different UEs and correctly estimate the timing of each of the UEs. In order to achieve that goal, the RACH preambles should have i) good cross-correlation properties to allow for accurate timing estimation of different simultaneous and asynchronous RACH preambles, ii) good auto-correlation properties to allow for accurate timing estimation, iii) zero cross-correlation for synchronous and simultaneous RACH preambles.
Long Term Evolution (LTE) wireless networks, also known as Evolved Universal Terrestrial Radio Access Networks (E-UTRAN), are being standardized by the 3GPP working groups. The Orthogonal Frequency Division Multiple Access (OFDMA) access scheme and the Single Carrier Frequency Division Multiple Access (SC-FDMA) access scheme were chosen for the downlink (DL) and the uplink (UL) of E-UTRAN, respectively. Signals from different User Equipments (UEs) to a base station are time and frequency multiplexed on a physical uplink shared channel (PUSCH). In the case that the UE is not UL synchronized, the UE uses a non-synchronized Physical Random Access Channel (PRACH) to communicate with the base station, and in response the base station provides UL resources and timing advance information to allow the UE to transmit on the PUSCH.
The 3GPP RAN Working Group 1 (WG1) has agreed on the preamble based physical structure of the PRACH (as described in “3GPP TS 36.211 Evolved Universal Terrestrial Radio Access (E-UTRA); Physical channels and modulation”). The RAN WG1 also agreed on the number of available preambles that can be used concurrently to minimize the collision probability between UEs accessing the PRACH in a contention-based manner. The Zadoff-Chu (ZC) sequence has been selected for RACH preambles for LTE networks.
A Zadoff-Chu sequence is a complex-valued mathematical sequence which, when used for radio signals, gives rise to a signal, whereby cyclically shifted versions of the signal do not cross-correlate with each other when the signal is recovered, for example at the base station. A generated Zadoff-Chu sequence that has not been shifted is known as a “root sequence”. The Zadoff-Chu sequence exhibits the useful property that cyclically shifted versions of the sequence remain orthogonal to one another, provided that each cyclic shift, when viewed within the time domain of the signal, is greater than the combined propagation delay and multi-path delay-spread of the signal as it is transmitted between the UE and base station.
The complex value at each position (n) of each root (μ) of the Zadoff-Chu sequence (for odd NZC, where NZC is the length of the Zadoff-Chu sequence) is given by:
                    x        μ            ⁡              (        n        )              =          e                        -          j                ⁢                              πμ            ⁢                                                  ⁢                          n              ⁡                              (                                  n                  +                  1                                )                                                          N            ZC                                ,                where 0≦n≦NZC−1.        
All of the RACH preambles are generated by cyclic shifts of a number of root sequences of the Zadoff-Chu sequence, which are configurable on a cell-basis. A RACH preamble is transmitted from a UE to the base station to allow the base station to estimate, and if needed, adjust the timing of the UE transmission. It has been agreed by the RAN WG1 that there are a total of 64 RACH preambles allocated for each cell of a base station. Specifically, a cell can use different cyclically shifted versions of the same ZC root sequence, or other ZC root sequences if needed, as RACH preambles. To maximize the number of available Zadoff-Chu sequences for a certain sequence length (NZC) it is preferred in one embodiment to choose the sequence length as a prime number, and therefore an odd number. Typically for LTE, the length of the Zadoff-Chu may be for example 839 or 139 depending on the format of the RACH preamble.
For the uplink in LTE wireless networks, SC-FDMA is used which is a single-carrier transmission based on Discrete Fourier Transform (DFT) spread OFDM. With reference to FIG. 1, the principle of SC-FDMA will now be described. FIG. 1 shows a user equipment 101 and a base station 121. The user equipment comprises a serial to parallel block 102 with a serial input for receiving a serial signal. The user equipment 101 further comprises an N-point Discrete Fourier Transform (DFT) block 104, a subcarrier mapping block 106, an M-point Inverse Discrete Fourier Transform (IDFT) block 108, a parallel to serial block 110, a Cyclic Prefixing (CP) and Pulse shaping (PS) block 112, a Digital to Analogue converter (DAC) and Radio Frequency (RF) converter block 114 and an antenna 116 for transmitting a signal over a channel 118 of the communication system. The serial to parallel block 102 has a parallel output coupled to a parallel input of the N-point DFT block 104. A parallel output of the N-point DFT block 104 is coupled to a parallel input of the subcarrier mapping block 106. A parallel output of the subcarrier mapping block 106 is coupled to a parallel input of the M-point IDFT block 108. A parallel output of the M-point IDFT block 108 is coupled to a parallel input of the parallel to serial block 110. A serial output of the parallel to serial block 110 is coupled to an input of the CP and PS block 112. An output of the CP and PS block 112 is coupled to an input of the DAC and RF converter block 114. An output of the DAC and RF converter block 114 is coupled to the antenna 116.
The base station 121 comprises an antenna 120 for receiving a signal over the channel 118 of the communication system. The base station further comprises a Radio Frequency (RF) converter and Analogue to Digital converter (ADC) block 122, a remove Cyclic Prefixing (CP) block 124, a serial to parallel block 126, an M-point Discrete Fourier Transform (DFT) block 128, a subcarrier demapping and equalization block 130, an N-point Inverse Discrete Fourier Transform (IDFT) block 132, a parallel to serial block 134 and a detection block 136 for detecting the signals.
A serial output of the antenna 120 is coupled to a serial input of the RF converter and ADC block 122. A serial output of the RF converter and ADC block 122 is coupled to a serial input of the remove CP block 124. A serial output of the remove CP block 124 is coupled to a serial input of the serial to parallel block 126. A parallel output of the serial to parallel block is coupled to a parallel input of the M-point DFT block 128. A parallel output of the M-point DFT block 128 is coupled to a parallel input of the subcarrier demapping and equalization block 130. A parallel output of the subcarrier demapping and equalization block 130 is coupled to a parallel input of the N-point IDFT block 132. A parallel output of the N-point IDFT block 132 is coupled to a parallel input of the parallel to serial block 134. A serial output of the parallel to serial block 134 is coupled to a serial input of the detection block 136.
In operation, for LTE uplink at the UE 101, a block of N modulation symbols are received at the serial to parallel block 102 and are applied as a parallel input to the N-point DFT block 104. The N-point DFT block 104 performs a discrete Fourier transform on the modulation symbols and then the output of the N-point DFT block 104 is applied to consecutive inputs of the M-point IFFT block 108 (where M>N) via the subcarrier mapping block 106. The output of the M-point IDFT block 108 is converted to a serial signal by the parallel to serial block 110 and a cyclic prefix is applied to each block of the serial signal in the CP and PS block 112. The signal is converted to an analogue signal and modulated at radio frequency in the DAC and RF converter block 114 before being transmitted using the antenna 116 over the channel 118 to the antenna 120 of the base station 121.
Since typically for a RACH preamble, a DFT of size N=839 or 139 needs to be taken (depending on the format of the preamble), the operation performed in the N-point DFT block 104 is demanding in terms of computational complexity and memory. One method for implementing a DFT where the size of the DFT is a prime number is the Bluestein algorithm (Leo I. Bluestein, “A linear filtering approach to the computation of the discrete Fourier transform,” Northeast Electronics Research and Engineering Meeting Record 10, 218-219 (1968)). In the Bluestein algorithm the DFT is re-expressed as a convolution which provides a way to compute prime-size DFTs with a computational complexity of the order O(N log N).
This disclosure relates to reducing the computational complexity required to perform a prime number DFT for use in processing a signal to be transmitted on a Random Access Channel.